/**
 * 时间复杂度
 */
// O(n^2) 数据量增大n倍时，耗时增大n的平方倍
for (let i = 0; i < n; i++) {
	for (j = 1; j < n; j++) {

	}
}
// O(n) 数据量的增大几倍，耗时也增大几倍
for (let i = 1; i < n; i++) {

}
// O(1) 如果算法的执行时间不随着问题规模n的增长而增长
let a = 1;
let b = 2;
// O(log2(n)) 当数据量增大n倍时，耗时增大logn倍，2为底。当数据量增大256倍时，耗时增大8倍
let i = 1;
while (i < n) {
	i *= 2
}


// 数组两项交换
function swap(arr, i, j) {
	let temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp
	return arr
}

// 去重
// 排序
let arr = [12, 8, 24, 16, 1];
// 冒泡
function bubble(arr) {
	let flag = false;
	for (let i = 0; i < arr.length - 1; i++) {
		for (let j = 0; j < arr.length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1)
				flag = true
			}
		}
		if (!flag) break
	}
}

// 插入
function insert(arr) {
	let handle = [];
	handle.push(arr[0]);
	for (let i = 1; i < arr.length; i++) {
		let A = arr[i]
		for (let j = handle.length - 1; j >= 0; j--) {
			let B = handle[j]
			if (A > B) {
				handle.splice(j + 1, 0, A)
				break
			}
			if (j === 0) {
				handle.unshift(A)
			}
		}
	}
}

// 快速排序
// 取出数组的中间项
// 拿每一项和中间项相比。比中间项小的放左边，比中间项大的放右边
// 依次把左边和右边做同样方式处理
// 直到某一边的数组是一项或者没有，则不再拆分
// 最后的结果。每一次都是把左边+中间+右边
function quick(arr) {
	if(arr.length <= 1) return arr;
	let middle = Math.floor(arr.length / 2); // 向下取整
	let value = arr.splice(middle, 1)[0];
	let arrLeft = [], arrRight = [];
	for(let i = 0; i < arr.length; i++) {
		let item = arr[i]
		item < value ? arrLeft.push(item) : arrRight(item)
	}
	return quick(arrLeft).concat(value, quick(arrRight))
}